package day04;

import java.util.Arrays;

/**
 * @author wangzhisen
 * @Desc TODO
 * @date 2025/4/11
 *
 * 冒泡排序
 */
public class BubbleDemo {
    public static void main(String[] args) {
        /*int[] arr ={12 , 9 , 27 , 6 , 78 , 45 , 23};
        System.out.println("排序前："+Arrays.toString(arr));*/

        int[] arr ={12 , 9 , 27 , 6 , 30 , 45 , 78};
        System.out.println("排序前："+Arrays.toString(arr));
        //sort1(arr);
        //sort2(arr);
        sort3(arr);

    }

    //未优化版本
    public static void sort1(int[] arr) {
        //i 控制比较的轮数
        for (int i = 0; i < arr.length-1; i++){
            System.out.println("===========目前比较第"+(i+1)+"轮===========");
            //j 控制比较的次数
            for (int j = 0; j < arr.length-i-1; j++){
                System.out.println("目前比较第"+(i+1)+"轮"+",第"+(j+1)+"次");
                if(arr[j] > arr[j+1]){
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
            System.out.println(Arrays.toString(arr));
        }
        System.out.println("排序后："+Arrays.toString(arr));
    }


    //优化1：优化轮数
    public static void sort2(int[] arr) {
        //i 控制比较的轮数
        for (int i = 0; i < arr.length-1; i++){
            System.out.println("===========目前比较第"+(i+1)+"轮===========");

            //标志位
            boolean flag = true;

            //j 控制比较的次数
            for (int j = 0; j < arr.length-i-1; j++){
                System.out.println("目前比较第"+(i+1)+"轮"+",第"+(j+1)+"次");
                //发生交换
                if(arr[j] > arr[j+1]){
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;

                    flag = false;
                }
            }

            //当不再发生交换时，则跳出循环
            if(flag){
                break;
            }
            System.out.println(Arrays.toString(arr));
        }
        System.out.println("排序后："+Arrays.toString(arr));
    }


    //优化2：优化次数
    public static void sort3(int[] arr) {
        //定义比较每一轮比较的次数的边界
        int position = arr.length-1;
        //i 控制比较的轮数
        for (int i = 0; i < arr.length-1; i++){
            System.out.println("===========目前比较第"+(i+1)+"轮===========");

            //标志位
            boolean flag = true;
            //记录最后一次比较的下标位置
            int limit = 0;

            //j 控制比较的次数
            for (int j = 0; j < position; j++){
                System.out.println("目前比较第"+(i+1)+"轮"+",第"+(j+1)+"次");
                //发生交换
                if(arr[j] > arr[j+1]){
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;

                    flag = false;

                    limit =j;
                }
            }
            position = limit;

            //当不再发生交换时，则跳出循环
            if(flag){
                break;
            }
            System.out.println(Arrays.toString(arr));
        }
        System.out.println("排序后："+Arrays.toString(arr));
    }
}
